package leetcode.code1415;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class Solution {
	List<String> list;
	char[] cs = new char[] { 'a', 'b', 'c' };

	public String getHappyString(int n, int k) {
		list = new ArrayList<>();
		char[] str = new char[n];
		this.f(0, str, n);
		if (list.size() < k) {
			return "";
		}
		Collections.sort(list);
		return list.get(k - 1);
	}

	private void f(int index, char[] str, int n) {
		if (index == n) {
			list.add(new String(str));
			return;
		}
		for (int i = 0; i < 3; i++) {
			if (index == 0 || cs[i] != str[index - 1]) {
				str[index] = cs[i];
				this.f(index + 1, str, n);
			}
		}

	}
}
